#define _CRT_SECURE_NO_WARNINGS 1



//L300
//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n, 1);
//        int ret = 1;
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[j] < nums[i]) {
//                    dp[i] = max(dp[j] + 1, dp[i]);
//                }
//            }
//            ret = max(ret, dp[i]);
//        }
//        return ret;
//    }
//};







//L376
//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n, 1), g(n, 1);
//        int fmax = 1, gmax = 1;
//
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[j] < nums[i]) {
//                    f[i] = max(f[i], g[j] + 1);
//                }
//                else if (nums[j] > nums[i]) {
//                    g[i] = max(g[i], f[j] + 1);
//                }
//            }
//            fmax = max(fmax, f[i]);
//            gmax = max(gmax, g[i]);
//        }
//        return fmax > gmax ? fmax : gmax;
//    }
//};




//L646
//class Solution {
//public:
//    int findLongestChain(vector<vector<int>>& pairs) {
//        sort(pairs.begin(), pairs.end());
//        int n = pairs.size();
//        vector<int> dp(n, 1);
//        int ret = 1;
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j < i; j++)
//                if (pairs[j][1] < pairs[i][0])
//                {
//                    dp[i] = max(dp[i], dp[j] + 1);
//                }
//        }
//        ret = max(ret, dp[i]);
//    }
//    return ret;
//}
//};





//L647
//
//class Solution {
//public:
//    int countSubstrings(string s) {
//        int n = s.size();
//        int ret = 0;
//        vector<vector<bool>> dp(n, vector<bool>(n));
//        for (int i = n - 1; i >= 0; i--) {
//            for (int j = i; j < n; j++) {
//                if (s[i] == s[j]) {
//                    if (i == j)
//                        dp[i][j] = true;
//                    else if (i + 1 == j) {
//                        dp[i][j] = true;
//                    }
//                    else {
//                        dp[i][j] = dp[i + 1][j - 1];
//                    }
//                    if (dp[i][j]) {
//                        ret++;
//                    }
//                }
//            }
//        }
//        return ret;
//    }
//};